【论文笔记】ConDySTA: Context-Aware Dynamic Supplement to Static Taint Analysis

2021-0408-ConDySTA: Context-Aware Dynamic Supplement to Static Taint Analysis

作者：Xueling Zhang, Xiaoyin Wang, Rocky Slavin, Jianwei Niu

单位：Department of Computer Science, University of Texas at San Antonio

会议：S&P 2021

论文链接：https://galadriel.cs.utsa.edu/~rslavin/publications/sp21.pdf

Introduction

污点分析（Taint Analysis）能够检测程序中的污点数据流，在软件与系统安全领域有广泛的应用：漏洞检测、隐私泄露检测、恶意软件检测等。污点分析的方法主要可以分为两大类：动态污点分析，在运行时根据实际运行的指令对污点进行传递，但是会遗漏未触发代码中的污点信息流，且存在较大的运行时开销；静态污点分析，会对所有可能的路径进行污点传播，从而检测所有可能的污点信息流，虽然不会有漏报，但是由于部分路径实际上是不可达的导致误报。

虽然静态污点分析理论上是sound的，但在real-world的各种复杂场景下经常会出现漏报的情况。之前的研究表明六款针对Android app state-of-the-art的静态分析工具均存在taint flow漏报。原因包括动态语言特性（反射调用）、动态加载/生成代码、外部代码执行以及多语言代码（native、shell script）。

因此作者提出了一种利用动态污点分析的结果辅助静态污点分析的方法（DySTA），以减少漏报。并通过 Monkey随机测试策略进行实验，表明可以减少大量的漏报。但是简单的使用动态分析结果会导致静态分析的context sensitivity丢失，作者又提出了hybrid context matching（ConDySTA），将动态分析得到的污点变量注入到静态分析对应上下文中的对应变量。

作者使用ReproDroid（a benchmarking framework for Android analysis tools）对DySTA和ConDySTA进行评估，DySTA 和 ConDySTA能够将ReproDroid中六款分析工具产生的28个漏报降低到12个。针对top 100 most downloaded Android app，ConDySTA能在FlowDroid检测出的281条taint flow的基础之上检测出39条taint flow。

本文的贡献如下：

• 证明了动态污点分析的结果能够作为静态污点分析的补充，以减少漏报。
• 开发了一种新的方法，ConDySTA，能够保留静态污点分析在使用动态污点分析结果时的context sensitivity。
• 使用ReproDroid benchmark and 100 top Android apps from Google Play进行实验，证明ConDySTA确实可以减少大量漏报。

Running Example and Approach Overview

Running Example

• Static Taint Analysis False Negative Example
  • blocker()和blocker2()是静态污点分析无法跟踪的函数，如写入文件与读取文件。
  • 若仅使用静态污点分析，第6行的inter不会被标记为污点变量，第10行到13行的taint flow会丢失。

DySTA Approach

DySTA：不包含hybrid context matching（ConDySTA）

DySTA会在首先静态污点分析后执行动态污点分析，并对分析的结果进行对比。发现Line 6的inter变量在动态污点分析时处于tainted状态，故会将inter设置为intermediate source，再次进行静态污点分析。此时Line 10～Line13的taint flow能够被检测出来，但是Line 15会出现误报（污点过标记）。

Code Analysis with the IFDS Framework

作者使用IFDS framework来解释这个问题。IFDS是一个能够进行inter-procedural, flow-sensitive, and context-sensitive analysis工具，基于exploded super graph（Fig.1）。

IFDS全称为Interprocedural，Finite，Distributive，Subset Problem，是一种基于图可达性的程序分析框架。名字直接反映了这个框架适用的问题范围：全程序（跨函数）的，分析对象的域是有限的，流函数满足分配律，必须满足以上条件才可以使用IFDS解决，IFDS相比传统的通过迭代算法到达格上的不动点角度的不同，它通过将程序看作一个图，并通过对图上的可达性来求解诸如到达定义这类静态分析问题。

• Taint flow的简单Example

  

Incorporating Context

获取到动态污点分析的调用栈s后，ConDySTA需要确定静态分析中的调用序列，C-context-matching。

ConDySTA根据C-context-matching创建了一个virtual fact v，通过其taint了inter。

Lack of Dynamic Taint-Propagation Paths

由于blocker函数的存在，仅使用Propagation-Based的动态污点分析同样很难处理blocker函数。作者使用value-based动态分析，但这种方法会导致propagate path缺失，即无法知道taint的来源。但是可以获得stack trace，需要解决的就是stack trace中有多少callsite是属于dynamic calling context的。

Approach

DySTA Algorithm

Dynamic Calling Context and Graph Extension

ConDySTA for Value-based Taint Analyses

Implementation

作者的ConDySTA，静态分析部分使用的是FlowDroid（a state-of-the-art tool based on IFDS framework），动态分析部分使用的是value-based动态污点分析（因为state-of-the-art propagation-based工具无法在Android 6.0以上使用）。虽然存在没办法处理加密数据、控制流依赖丢失的缺点，但是value-based在处理全黑盒的情况下存在较大的优势（API实现在remote server等）。

User Profile For Tainted Values

ConDySTA将User Profile作为value-based动态污点分析的value。

Intermediate Source Collection

ConDySTA对所有返回类型为java.lang.String的函数进行插桩以收集其返回值。

重打包后，使用Monkey浏览应用程序20秒，收集日志中插桩得到的信息。

Applying FlowDroid

ConDySTA首先使用FlowDroid进行第一轮的静态污点分析，以减少动态分析得到的intermediate source的数量（去重）。通过动态分析收集到intermediate source后，再次提供给FlowDroid运行。

Evaluation

数据集：ReproDroid中的部分样本（包含ground truth的小程序）、Google Play 100 most downloaded apps。

对比的六款state-of-the-art静态污点分析工具：Amandroid, DIALDroid, DidFail, DroidSafe, FlowDroid, IccTA

Research Questions and Summarized Answers

• ConDySTA可以检测taint flow数量比仅静态分析多
  • 六款state-of-the-art静态分析工具在分析ReproDroid benchmark的时候会存在28个漏报，ConDySTA可以检测出其中的12个。（Table II）
  • 100个real-world apps中ConDySTA在12个app中检测到的taint flow比FlowDroid多39条taint flow，ConDySTA共计在57个app中检测到281条taint flow，被污点标记的信息包括email addresses, country, language, device’s manufacturer, advertising ID, user’s full name and username。
• 与单纯的动态分析补充相比，上下文敏感可以减少多少误报？
  • benchmark中DySTA检测到21 taint flows（12 true positives, 9 false positives），ConDySTA可以减少9个false positives。
  • real-world app中可以减少1029个上下文不匹配的taint flow
• ConDySTA与单纯污点分析检测taint flows的对比
  • 39个中仅使用动态分析检测到19个。
• 时间开销
  • 1s～4266s，与FlowDroid相当。

Evaluation on the Benchmark

ICC：Inter Component Communications

Evaluation on Real World Apps

3～6列含义：

• Additionally Detected Flows Over FlowDroid
• ConDySTA vs. DySTA
• Comparison with Pure Dynamic Taint Analysis
• Execution Time

Conclusion

作者使用动态污点分析的方式以提高静态污点分析的准确性，兼顾性能与精度，虽然是实现在android/java，但思路值得我们学习。ConDySTA动态污点分析实现方式较为粗糙，静态分析也主要是借助于FlowDroid，主要贡献在于对现有的针对Android的污点分析效果有所提升、能够将context-aware较为形式化的展现出来。